Merge Sort

原理：利用將兩有序數組合併只需要線性時間的特性將數組分割，合併

思考&衍伸：

1. 合併有序數組的技巧：在有序數組後放一個大數(可以解決長度的問題)
2. 時間複雜度O(n logn)
3. 有效排序鏈表

void merge_sort(vector<int>& arr, int l, int r){
    if(l>=r){
        return;
    }
    int mid = (r+l)/2;
    merge_sort(arr, l, mid);
    merge_sort(arr, mid+1, r);
    
    vector<int> l_arr(arr.begin()+l, arr.begin()+mid+1);
    vector<int> r_arr(arr.begin()+mid+1, arr.begin()+r+1);
    l_arr.insert(l_arr.end(), INT_MAX);
    r_arr.insert(r_arr.end(), INT_MAX);
    int i = 0,j = 0;
    for(int k = l;k<=r; k++){
        if(l_arr[i]<=r_arr[j]){
            arr[k] = l_arr[i];
            i++;
        }
        else{
            arr[k] = r_arr[j];
            j++;
        }
    }
}

不反復宣告子陣列的寫法

傳入與arr大小相同的split陣列

void merge_sort(vector<int>& arr, vector<int> split, int l, int r){
    if(l>=r){
        return;
    }
    int mid = (r+l)/2;
    merge_sort(arr, split,l, mid);
    merge_sort(arr, split,mid+1, r);
    for(int i = l; i<r+1; ++i){
        split[i] = arr[i];
    }
    int i = l,j = mid+1;
    for(int k = l;k<=r; k++){
        if(i==mid+1){
            arr[k] = split[j++];
        }
        else if(j==r+1){
            arr[k] = split[i++];
        }
        else if(split[j]<split[i]){
            arr[k] = split[j++];
        }
        else{
            arr[k] = split[i++];
        }
    }
}

例題實戰

21. Merge Two Sorted Lists
這題雖然不算是Merge Sort...但有用到合併的操作，所以放入例題(等等下一題會用到)
遞迴比較直觀，可讀性也高，迭代的細節寫在註解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {

        // 遞迴法
        // if(l1==NULL)
        //     return l2;
        // if(l2==NULL)
        //     return l1;
        // if(l1->val < l2->val){
        //     l1->next = mergeTwoLists(l1->next, l2);
        //     return l1;
        // }
        // else{
        //     l2->next = mergeTwoLists(l2->next, l1);
        //     return l2;
        // }
        // return l1;

        //迭代法
        ListNode* preHead = new ListNode(-1);
        ListNode* preHead_temp = preHead; // 用於保留root節點
        while(l1!=NULL && l2!=NULL){
            if(l1->val < l2->val){
                preHead->next = l1;
                l1 = l1->next;  
            }
            else{
                preHead->next = l2;
                l2 = l2->next;
            }
            preHead = preHead->next;
        }

        // 最後會剩l1或是l2，將其合併進去
        if(l1!=NULL){
            preHead->next = l1;
        }
        else{
            preHead->next = l2;
        }
        return preHead_temp->next;

    }
};

148. 排序链表
如果有寫過上面那一題，就會發現Merge Sort拿來排序鏈表很適合~~

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if(head==nullptr||head->next==nullptr){
            return head;
        }
        ListNode* first_right_node = cut_from_mid(head);
        ListNode* right = sortList(head);
        ListNode* left = sortList(first_right_node);
        ListNode* res = merge(right, left);
        return res;
    }

    //將List從中間分割成左鏈和右鏈，返回第一個右鏈節點
    ListNode* cut_from_mid(ListNode* head){
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* slow_f = nullptr; //走在slow後面，用於斷開左右鏈
        while(fast&&fast->next){
            slow_f = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        slow_f->next = nullptr; //斷開左右鏈
        return slow; //回傳右鏈第一個節點
    }
    //預設左右長度只差1 (分割時保證)
    ListNode* merge(ListNode* left, ListNode* right){
        ListNode* new_head = new ListNode();
        ListNode* curr = new_head;
        while(left&&right){
            if(left->val < right->val){
                curr->next = left;
                left = left->next;
            }
            else{
                curr->next = right;
                right = right->next;
            }
            curr = curr->next;
        }
        curr->next = left?left:right;
        return new_head->next;
    }
};

剑指 Offer 51. 数组中的逆序对
經典的Merge Sort應用，合併兩個排序數組時，可以順便統計逆序對
特別解釋一下程式碼中更新res的mid-i+1
在tmp[i]>tmp[j]情況下，保證tmp[i]~tmp[mid]都比tmp[j]大，而這些都會形成逆序對，所以逆序對增加mid-i+1!!
有這個理解下，這題只是要實現一下Merge Sort而已

class Solution {
    int res = 0;
public:
    int reversePairs(vector<int>& nums) {
        /*
        思路：
        merge sort合併兩個有數組時計算有多少逆序對
        */
        int n = nums.size();
        vector<int> tmp(n);
        merge_sort(0, n-1, nums, tmp);
        return res;
    }
    void merge_sort(int l, int r,vector<int>& nums, vector<int>& tmp){
        if(l>=r){
            return;
        }
        int mid = (l+r)/2; //mid是左數組的尾
        merge_sort(l, mid, nums, tmp);
        merge_sort(mid+1, r, nums, tmp);
        //利用tmp保存兩有序數組, tmp[l]~tmp[mid]是左數組, tmp[mid+1]~tmp[r]是右數組
        for(int k = l; k<=r; ++k){
            tmp[k] = nums[k];
        }
        int i = l, j = mid+1;
        for(int k = l; k<=r; ++k){
            if(i>mid){
                nums[k] = tmp[j++];
            }
            else if(j>r){
                nums[k] = tmp[i++];
            }
            else if(tmp[i]<=tmp[j]){
                nums[k] = tmp[i++];
            }
            else{ //tmp[j]<tmp[i] 出現逆序對
                nums[k] = tmp[j++];
                res+=mid-i+1;
            }
        }
    }
};

Merge Sort的分治思路很容易在題目出現，刷過幾題之後出現類似的題目會好思考一點(?